package done.normal_601_700;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 654. Maximum Binary Tree 最大二叉树
 * <p>
 * 给定一个不含重复元素的整数数组。一个以此数组构建的
 * 最大二叉树定义如下：二叉树的根是数组中的最大元素。
 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
 * <p>
 * Example 1:
 * 输入: [3,2,1,6,0,5]
 * 输入: 返回下面这棵树的根节点：
 * <p>
 * 6
 * /   \
 * 3     5
 * \    /
 * 2  0
 * \
 * 1
 *
 * @author 大硕
 * 2019-04-16 10:44 PM
 **/
@SuppressWarnings("all")
public class MaximumBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 190416 first
        // 190417 second
        return null;
    }

    @Test
    public void test() {
        int[] nums = new int[]{3, 2, 1, 6, 0, 5};
        info(constructMaximumBinaryTree(nums));
    }
}










































/*
public TreeNode constructMaximumBinaryTree(int[] nums) {
    return dfs(nums,0,nums.length-1);
}

public TreeNode dfs(int[] nums,int begin,int end) {
    if (begin <= end) {

        int t = getMax(nums, begin, end);

        TreeNode root = new TreeNode(nums[t]);
        root.left = dfs(nums, begin, t-1);
        root.right = dfs(nums, t+1, end);
        return root;
    }
    return null;
}

//获取最大元素下标
public int getMax(int[] nums, int begin, int end){
    int ans = begin;
    for (int i = begin+1; i <= end; i++)
        if (nums[i] > nums[ans])
            ans = i;

    return ans;
}
*/
